This application is based upon and claims the benefit of priority from the prior Japanese Patent Application No. 11-257986, filed Sep. 10, 1999; the entire contents of which are incorporated herein by reference.
1. Field of the Invention
The present invention relates to a decoding for variable length code words, and, more particularly, relates to a decoding method and a decoding apparatus for generating tables and detecting a code length of each code word after coding and for generating an address in the table in which decoded data items are stored, and also relates to a computer readable recording medium in which a decoding program is stored.
2. Description of the Related Art
There is a conventional decoding apparatus for decoding a variable length code word consisting of a definition part and a real data part, as shown in FIG. 1, for example. The definition part of the variable length code word includes the number of code words corresponding to each code length and decoded data items corresponding to each code word.
FIG. 1 is a block diagram showing a configuration of the conventional decoding apparatus.
As shown in FIG. 1, the conventional decoding apparatus comprises tables T1, T2, and T3, a buffer memory 11 for storing the real data part in the bit stream including variable length code words, a code word separation circuit 12 capable of separating one bit from the real data part stored in the buffer memory 11, a comparator 13 for comparing an output data item from the code word separation circuit 12 with the data items stored in the table T3, and an addition circuit 14 for adding the output from the comparator 3 to an output data item obtained from the table T2.
The table T1 stores the decoded data items included in the definition part that are arranged in smaller order of the codewords. The table T2 stores the address to be used for searching the table T1, and the address indicates a memory field storing the decoded data item for the smallest value in code words having a same code length. In the table T2, the code length is used as index. The table T3 stores the code word of the smallest value in code words having a same code length. In the table T3, the code length is also used as index.
There is a following conventional decoding method of decoding variable length code words in JPEG, for example.
At first, the tables T1 to T3 are generated by analyzing the definition (see FIG. 2) included in the head part of the bit stream. FIG. 2 shows an example of the definition stored in the head part in which the number of code words having a code length 0 is zero, the number of code words having a code length 2 is two, the number of code words having a code length 3 is one, the number of code words having a code length 4 is two, and the number of code words having a code length 5 is two.
The generation methods of the tables T1 to T3 will be explained in detail.
At first, as shown in FIG. 3, the code (HUFFCODE(k)) corresponding to each code length (HUFFSIZE(k)) is obtained based on the number of code words. In the example shown in FIG. 3, the first code word (as the smallest code) in the code words having the code length 2 is determined as xe2x80x9c00xe2x80x9d, and the second code word is determined as xe2x80x9c0xe2x80x9d because the number of code words having the code length 2 is only two. Similarly, the first code (as the smallest code) in the code words having the code length 4 is determined as xe2x80x9c1010xe2x80x9d, and the second code is determined as xe2x80x9c1011xe2x80x9d because the number of code words having the code length 4 is also two. In this example, each code is expressed under the binary system. The decoded data item corresponding to each code word is separated from the head part and then stored in the table T1. In addition, as shown in FIG. 4, the smallest code word in code words having a same code length (namely, per same code length) is stored in the table T3 according to each code length as index. Further, the first address in the table T1 in which the decoded data items corresponding to the smallest code word in code words having a same code length are stored is stored in the table T2, as shown in FIG. 6.
An actual decoding process that uses the tables T1, T2, and T3 made by the above-described manner can be executed under the following procedures.
FIG. 7 is a flow chart showing the procedures of the conventional decoding method of decoding variable length code words. At first, the bit stream is stored in the buffer memory 11 in first-in order. The value xe2x80x9czeroxe2x80x9d is set to a register xe2x80x9ctempxe2x80x9d as an initial value, and the value xe2x80x9c1xe2x80x9d is set to a counter xe2x80x9cixe2x80x9d as an initial value (Step S301).
The following operation is then performed by using the counter xe2x80x9cixe2x80x9d that indicates a code length.
First, the first bit in the data stored in the buffer memory 11 is read and then added into the end of the register xe2x80x9ctempxe2x80x9d. Next, the comparator 13 compares the value of the register xe2x80x9ctempxe2x80x9d with the smallest code word T3 (i) in code words having the code length xe2x80x9cixe2x80x9d (where xe2x80x9cixe2x80x9d is a positive integer) (Step S303).
The symbol xe2x80x9cbits[i]xe2x80x9d in FIG. 7 indicates the xe2x80x9ci-thxe2x80x9d bit in the codes. Because the maximum code length in JPEG is 16, these operations are repeated from i=1 to i=16 (Steps S302 to S305). As a result, when it is firstly detected at Step S303 in this repeating process that the value T3(i) is greater than the value of the register xe2x80x9ctempxe2x80x9d, the code length xe2x80x9clengxe2x80x9d becomes xe2x80x9cixe2x88x921xe2x80x9d (Steps S305 and S306 ). On the other hand, when xe2x80x9cixe2x80x9d is not detected in the comparison at Step S303, the code length becomes 16 (Step S305 and S306 ). Thereby, the code word is determined as the xe2x80x9clengxe2x80x9d bits from the first bit to the xe2x80x9c(ixe2x88x921)xe2x88x92thxe2x80x9d bit (see xe2x80x9cleng=ixe2x88x921 and word=bits[1:ixe2x88x921]xe2x80x9d at Step S306 ). Thus, the code word xe2x80x9cwordxe2x80x9d is expressed by bits[1:ixe2x88x921] in FIG. 7.
Then, the address T2(leng) in the table T1 indicating the smallest code word in the code words having the code length xe2x80x9clengxe2x80x9d in the table T1 by referring the table T2 by using the code length xe2x80x9clengxe2x80x9d as index. In addition, an offset (as a difference) from the smallest code word in the same code length can be obtained by subtracting the smallest code word T3(leng) having the same code length xe2x80x9clengxe2x80x9d from the code word xe2x80x9cwordxe2x80x9d (Step S307 ).
After this step S307, the value xe2x80x9caddrxe2x80x9d of the pointer (hereinafter referred to as pointer xe2x80x9caddrxe2x80x9d) is calculated by adding the offset xe2x80x9coffsxe2x80x9d to T2(leng) (Step S308). The table T1 is searched by using this pointer in order to obtain the decoded data item corresponding to the code word xe2x80x9cwordxe2x80x9d (Step S309).
For example, FIG. 5 shows the value of each variable at Step S303 when the first bit in the bit stream is xe2x80x9c1011011011101101xe2x80x9d. That is, the condition xe2x80x9ctem T3(i)xe2x80x9d is recognized at Step S303 when xe2x80x9cixe2x80x9d=5 (temp=10110). Thereby, xe2x80x9clengxe2x80x9d=5xe2x88x921=4 is calculated at Step S306. Because T3=xe2x80x9c1010xe2x80x9d when xe2x80x9clengxe2x80x9d=4(see FIG.4 ), the offset xe2x80x9coffsxe2x80x9d becomes 1 (offs=1011xe2x88x921010=1). The address xe2x80x9caddrxe2x80x9d of the decoded data item in the table T1 can be calculated by adding this offset xe2x80x9coffsxe2x80x9d to the first address T2 when i=4. The decoded data item is then obtained based on the address xe2x80x9caddrxe2x80x9d. As shown in FIG. 6, the decoded data item xe2x80x9cdata (V4,1)xe2x80x9d stored in the table T1 can be obtained by using a new index calculated by adding the offset xe2x80x9coffsxe2x80x9d to the first address obtained from the table T2.
By using the manner described above, the decoding for a code word is completed. When the decoding for the following code word is performed, the decoding apparatus eliminates the data item of the code length xe2x80x9clengxe2x80x9d from the buffer memory 11, or shifts the pointer to the first bit in the following code word to be decoded in order to point the first bit in the following code word.
However, in the conventional decoding apparatus, the overhead to generate the tables T1 to T3 occurs because the table T3 that stores the smallest code word in code words per code length must be generated based on the definition part in the variable length code word. That is, in the decoding of the bit stream in JPEG, there is a drawback that the overhead of the generation of the tables becomes large because the various variable length tables are defined based on the number of code words per code length. Furthermore, because the size of the table T3 is determined based on the maximum number of code words per code length, it must be necessary to prepare 136 bits (=1+2+3+4+5+6+7+8+9+10+11+12+13+14+15+16) in a hard logic, or to prepare 256 bits (16 bitsxc3x9716) in a RAM, there is a drawback that the entire size of the memory storing the tables T1, T2, and T3 in the conventional decoding apparatus becomes large. Moreover, because the size of the comparator 13 for comparing each code word with the smallest value in code words per code length becomes 16 bits. These drawbacks of the conventional decoding apparatus cause to increase the entire size of the decoding apparatus itself and to reduce the decoding speed.
Accordingly, an object of the present invention is, with due consideration to the drawbacks of the conventional technique, to provide a decoding method and a decoding apparatus capable of increasing a decoding speed and capable of decreasing the entire size of the decoding apparatus by reducing the size of each table to be used during the decoding process, and to provide a computer readable recording medium in which a decoding program is stored.
In accordance with a preferred embodiment of the present invention, a decoding method of decoding variable length code words consisting of a definition part and a real data part formed by a code word sequence. In the definition part, the number of code words corresponding to each code length and decoded data items corresponding to the code words are defined. The decoding method has the steps of making a table in which the number of code words corresponding to each code length as index is stored, setting an initial value xe2x80x9c1xe2x80x9d to a pointer, performing following steps (1) and (2) from the minimum value in the code lengths as index in the table in increasing order: (1) adding one bit in the code word sequence in the real data part designated by the pointer to the end of a register; and (2) comparing a value in the table corresponding to the code length as index with the value of the register, and subtracting the value in the table from the value of the register, and adding the value of the pointer by xe2x80x9c1xe2x80x9d when the value of the register is not less than the value of the table. The decoding method further has repeating the steps (1) and (2) based on the following code length as index and the value of the register after the subtraction, detecting the current code length as index for the code length of a target code word to be detected when the value of the register is smaller than the value of the table at the step (2), and specifying the decoded data item corresponding to the code word based on the value of the register and the detected code length.
Accordingly, when compared with the conventional decoding method to make and use a table storing the minimum value or the maximum value in code words having each code length based on the code length as index, because the decoding method of the present invention makes and uses the table storing the number of code words having each code length based on the code length as index, it is possible to reduce the overhead of the memory size to store the table and to perform the decoding process easily at a high speed.
Furthermore, the decoding method as another preferred embodiment of the present invention has the steps of adding accumulatively the number of code words from the minimum value of the code length to the detected code length as index, and using an address, in order to get a target decoded data item, obtained by adding the accumulated value of the number of code words to the current value of the register.
Accordingly, it is possible to use no table in which the addresses indicating the minimum value or the maximum value in code words per code length based on the code length as index when the addresses in a table in which decoded data items are stored. This can reduce the memory size and performs the decoding process at a high speed.
In accordance with a preferred embodiment of the present invention, a decoding apparatus for decoding variable length code words consisting of a definition part and a real data part formed by a code word sequence. In the definition part, the number of code words corresponding to each code length and decoded data items corresponding to the code words are defined. Thee decoding apparatus has a memory section, a pointer, and a comparison arithmetic operation section. The memory section stores a table in which the number of code words corresponding to each code length as index is stored. An initial value of the pointer is xe2x80x9c1xe2x80x9d. The comparison arithmetic operation section performs following operations (1) and (2) from the minimum value in the code lengths as index in the table in increasing order: (1) adding one bit in the code word sequence in the real data part designated by the pointer to the end of a register; and (2) comparing a value in the table corresponding to the code length as index with the value of the register, and subtracting the value in the table from the value of the register, and adding the value of the pointer by xe2x80x9c1xe2x80x9d when the value of the register is not less than the value of the table. In the decoding apparatus of the preferred embodiment, the comparison arithmetic operation section repeats the operations (1) and (2) based on the following code length as index and the value of the register after the subtraction, and detects the current code length as index for the code length of a target code word to be detected when the value of the register is smaller than the value of the table at the operation (2), and specifies the decoded data item corresponding to the code word based on the value of the register and the detected code length.
Accordingly, when compared with the conventional decoding apparatus to use a table storing the minimum value or the maximum value in code words having each code length based on the code length as index, because the present invention uses the table of a small size to store the number of code words having each code length based on the code length as index, it is possible to reduce the memory size to store the table and to reduce the overhead of the comparator. This can cause to provide the decoding apparatus of a small size and to perform the decoding process easily at a high speed.
Furthermore, the decoding apparatus as another preferred embodiment of the present invention further has an accumulative addition circuit for accumulatively adding the number of code words from the minimum value of the code length to the detected code length as index. In the decoding apparatus, the comparison arithmetic operation section uses an address, in order to get a target decoded data item, obtained by adding the accumulated value of the number of code words obtained from the accumulative addition circuit to the current value of the register.
Accordingly, it is possible to use no table in which the addresses indicating the minimum value or the maximum value in code words per code length based on the code length as index when the addresses in a table in which decoded data items are stored. This can reduce the memory size and apply the remained memory to another purpose efficiently.
In accordance with a preferred embodiment of the present invention, a computer readable recording medium for storing a decoding program for decoding variable length code words consisting of a definition part and a real data part consisting of a code word sequence, and in the definition part the number of code words corresponding to each code length and decoded data items corresponding to the code words are defined, the recording medium storing the decoding program comprising the steps of: making a table in which the number of code words corresponding to each code length as index is stored; setting an initial value xe2x80x9c1xe2x80x9d to a pointer; performing following steps (1) and (2) from the minimum value in the code lengths as index in the table in increasing order: (1) adding one bit in the code word sequence in the real data part designated by the pointer to the end of a register; and (2) comparing a value in the table corresponding to the code length as index with the value of the register, and subtracting the value in the table from the value of the register, and adding the value of the pointer by xe2x80x9c1xe2x80x9d when the value of the register is not less than the value of the table. The decoding program further has the steps of repeating the steps (1) and (2) based on the following code length as index and the value of the register after the subtraction; detecting the current. code length as index for the code length of a target code word to be detected when the value of the register is smaller than the value of the table at the step (2); and specifying the decoded data item corresponding to the code word based on the value of the register and the detected code length.
The computer readable recording medium as another preferred embodiment further has the steps of: adding accumulatively the number of code words from the minimum value of the code length to the detected code length as index, and using an address, in order to get a target decoded data item, obtained by adding the accumulated value of the number of code words to the current value of the register.
Accordingly, it is possible to store the decoding program capable of reducing the size of a memory and available to transfer it because of the reduction of the tables and of easy execution of the decoding process at a high speed. In addition, it is also possible to realize the decoding method and the decoding apparatus described above by installing the decoding program stored in the recording medium to a general purpose computer such as a personal computer and the like.